#include <iostream>
#include <vector>
#include <map>

using namespace std;

struct ListNode
{
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
 
//VS2010 

class Solution
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
	{
		vector<int> val1;
		vector<int> val2;
		

		while(l1)
		{
			val1.push_back(l1->val);
			l1=l1->next;
		}

		while(l2)
		{
			val2.push_back(l2->val);
			l2=l2->next;
		}

		vector<int>* vMin;
		vector<int>* vMax;
		vector<int> result;

		if(val1.size()>val2.size())
		{
			vMin=&val2;
			vMax=&val1;
		}
		else
		{
			vMin=&val1;
			vMax=&val2;
		}

		int addResult;
		int flag=0;

		for(size_t i=0;i<vMin->size();++i)
		{
			addResult=flag+vMin->at(i)+vMax->at(i);
			if(addResult>=10)
			{
				flag=1;
			}
			else
			{
				flag=0;
			}
			result.push_back(addResult%10);
		}
		for(size_t i=vMin->size();i<vMax->size();++i)
		{
			addResult=flag+vMax->at(i);
			if(addResult>=10)
			{
				flag=1;
			}
			else
			{
				flag=0;
			}
			result.push_back(addResult%10);
		}

		if(flag)
		{
			result.push_back(1);
		}

		ListNode *header=new ListNode(0);
		ListNode *lst=header;

		for(size_t i=0;i<result.size()-1;++i)
		{
			lst->val=result[i];
			lst->next=new ListNode(0);
			lst=lst->next;
		}
		lst->next=NULL;
		lst->val=result[result.size()-1];

		return header;
    }
};

int main()
{
	Solution s;
	ListNode l1(1);
	l1.next=new ListNode(8);

	ListNode l2(0);

	s.addTwoNumbers(&l1,&l2);

	return 0;
}